package com.公司笔试草稿;

import java.util.*;

public class work02 {

}


class Solution02 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param harmList  int整型一维数组 杀伤力数组
     * @param totalHarm int整型 需要组合出来的总的杀伤力
     * @return int整型
     */
    public int solution(int[] harmList, int totalHarm) {
        // write code here
        //    动态规划 凑零钱

        // 数组大小为 amount + 1，初始值也为 amount + 1
        int[] dp = new int[totalHarm + 1];

        // 凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币）
        for (int i = 1; i < dp.length; i++) {
            // 不可能超过这个值
            dp[i] = totalHarm + 1;
        }

        for (int i = 0; i < dp.length ; i++) {
            for (int harm : harmList) {
                // 一个硬币的值就超过了要凑的钱
                if (i < harm) {
                    continue;
                }
                if (i == harm) {
                    dp[i] = 1;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - harm]);
            }
        }

        return (dp[totalHarm] == totalHarm + 1) ? -1 : dp[totalHarm];
    }


    public int coinChange(int[] coins, int amount) {
        // 数组大小为 amount + 1，初始值也为 amount + 1
        int[] dp = new int[amount + 1];

        // 凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币）
        for (int i = 1; i <= dp.length - 1; i++) {
            dp[i] = amount + 1;
        }


        for (int i = 0; i <= dp.length - 1; i++) {
            for (int coin : coins) {
                // 一个硬币的值就超过了要凑的钱
                if (i < coin) {
                    continue;
                }
                if (i == coin) {
                    dp[i] = 1;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }


    public static void main(String[] args) {
        int[] test = {1, 2, 5};
//        Solution0
        Solution02 work = new Solution02();
//        int res = work.coinChange(test, 11);

        int res = work.solution(test, 11);
        System.out.println(res);
    }
}